package 哈希表;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/8 18:36
 */
public class lc167两数之和II {





    /*
     双指针直接妙 , 因为给定的数组 已经排好序
     */
    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length - 1 ,ans[] = null ;
        while(l < r){
            if(nums[l] + nums[r] == target){
                ans = new int[]{l + 1,r + 1};
                break;
            }else if(nums[l] + nums[r] < target){
                l++;
            }else{
                r--;
            }
        }
        return ans;
    }


    /*
      遍历 + 二分
     */
    public int[] solve(int nums[],int target){
        int r = 0;
        for(int i = 0;i < nums.length - 1;i++ ){
            if((r = binarySearch(nums,target - nums[i]) )!= - 1){
                return new int[]{i + 1,r + 1};
            }
        }
        return  null;
    }

    public int binarySearch(int nums[],int val){
        int l = 0, r = nums.length - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] > val){
                r = mid - 1;
            }else{
                l = mid;
            }
        }
        return  nums[l] == val ? l : -1;
    }

    // 生成测试用例测试 上面的二分查找
    public static void main(String[] args) {
        int nums[] = new int[]{2,7,11,15};
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        lc167两数之和II lc = new lc167两数之和II();
        System.out.println(lc.binarySearch(nums,9));
    }

}
